public class MyLinkedList implements IList {

    //
    class ListNode {
        int val;
        ListNode next;
        ListNode pre;
        ListNode(int x) {
            val = x;
        }
    }

    ListNode head = null;
    ListNode last = null;//还要多一个“尾巴”

    @Override
    public void addFirst(int data) {

        //根据参数，生成新节点
        ListNode newNode = new ListNode(data);

        //原链表没有节点
        if (head == null) {

            head = newNode;
            last = newNode;

            return;

        }

        //原列表有节点
        head.pre = newNode;
        newNode.next = head;
        head = newNode;

        return;

    }

    @Override
    public void addLast(int data) {

        //生成新节点
        ListNode newNode = new ListNode(data);

        //原链表没有节点
        if (head == null) {

                newNode.pre = last;
                last = newNode;
                head = newNode;

                return;

        }

        //原链表有节点
        newNode.pre = last;
        last.next = newNode;
        last = newNode;

        return;


    }

    @Override
    public void addIndex(int index, int data) {


        //先检查 所给下标是否合法
        if(index<0 ||index>size()){//不合法

            //抛出自定义异常
            try{

                throw new IndexIsNotLegal("所给下标 不合法！！！");

            }catch(IndexIsNotLegal e){


                e.printStackTrace();
                System.out.println("出错啦！！！"+e.getMessage());

            }
            return;//是否需要return？？？
        }



        //合法
        //生成节点  插入
        ListNode newNode = new ListNode(data);


        //判断原链表是否为空
        if(this.head == null){

            //newNode.pre = last;
            last = newNode;
            head = newNode;

            return;

        }

        int count = 0;//这里 默认 index 为 从0开始的下标
        ListNode cur = head;//用cur来遍历链表
        /*while(cur.next != null){

            if(count < index-1){

                count++;

            }

            //cur到达下标为index-1位置
            newNode.pre = cur;
            newNode.next = cur.next;
            cur.next.pre = newNode;
            cur.next = newNode;
            return;

        }*/
        while(count<index-1){

            count++;
            cur = cur.next;
        }
        //cur到达下标为index-1位置


        newNode.pre = cur;
        newNode.next = cur.next;

        if(cur.next == null){
            cur.next = newNode;
            last = newNode;
            return;

        }
        cur.next.pre = newNode;
        cur.next = newNode;


    }

    @Override
    public boolean contains(int key) {

        if(this.head == null){
            //System.out.println("所给链表为空，无法删除");
            return false;

        }

        ListNode cur = head;
        while(cur != null){

            if(cur.val == key){

                return true;

            }
            cur = cur.next;

        }

        return false;
    }

    @Override
    public void remove(int key) {

        //先看有没有这个元素
        if(!contains(key)){//没有
            System.out.println("没有这个元素，删不了。");
            return;

        }

        //有这个元素
        ListNode cur = head;


        while(cur.next!=null){

            if(cur==head&&cur.val==key){
                //cur.next.pre==null;
                cur = cur.next;
                cur.pre =null;
                head =cur;
                return;

            }

            if(cur.val == key){
                cur.pre.next = cur.next;
                cur.next.pre = cur.pre;

                return;
            }
            cur = cur.next;

        }
        //还差最后 一个 元素
        if(last.val == key){
            last = last.pre;
            last.next = null;
        }

    }

    @Override
    public void removeAllKey(int key) {

        if(!contains(key)){
            //不存在这个元素
            System.out.println("不存在这个元素");
            return;

        }

        ListNode cur = head;

        if(cur==head&&cur.val==key){
            //cur.next.pre==null;
            cur = cur.next;
            cur.pre =null;
            head =cur;

        }
        while(cur.next != null){

            if(cur.val == key){
                /*cur.next = cur.next.next;
                cur.next.pre = cur;*/
                cur.pre.next = cur.next;
                cur.next.pre = cur.pre;
            }
            cur = cur.next;

        }
        //还差最后 一个 元素
        if(last.val == key){
            last = last.pre;
            last.next = null;
        }

    }

    @Override
    public int size() {

        int count = 0;
        ListNode cur = head;
        while(cur != null){

            count++;
            cur = cur.next;

        }
        return count;
    }

    @Override
    public void clear() {

        head = null;
        last = null;

    }

    @Override
    public void display() {

        ListNode cur = head;
        while(cur != null){

            System.out.println(cur.val);
            cur = cur.next;

        }

    }
}
